package com.tgy.排序;

import java.util.Arrays;

/***
 * @ClassName: CountingSort
 * @Description: 计数排序
 * @Auther: tanggy3
 * @Date: 16:43 2022/8/30
 * @version : V1.0
 */
public class CountingSort {
    public static void main(String[] args) {
        int arr[] = {53, 3, 2, 748, 14, 214};
        System.out.println(Arrays.toString(getArrCountF(arr)));
        System.out.println(Arrays.toString(countingSortF(arr)));
    }

    /**
     * 只有正数
     *
     * @param arr
     * @return
     */
    static int[] countingSort(int[] arr) {
        int[] bucket = new int[getArrCount(arr)];
        for (int i : arr) {
            bucket[i]++;
        }
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            for (int j = 0; j < bucket[i]; j++) {
                arr[index++] = i;
            }
        }
        return arr;
    }

    /**
     * 可以有负数
     * 在程序中处理掉最小值，其实也是一种变相的优化
     * @param arr
     * @return
     */
    static int[] countingSortF(int[] arr) {
        int[] arrCount = getArrCountF(arr);
        int count = arrCount[0];
        int min = arrCount[1];
        int max = arrCount[2];
        int[] bucket = new int[count];
        for (int i : arr) {
            /**
             * 桶的编号减去最小值
             * 补上最小的那个值，有负数的情况下就相当于把数列整体右移，使其全部为正数
             * 全部为非负数的情况下，相当于缩小了数组长度，长度变为最大值与最小值的差值（小优化）
             */
            bucket[i - min]++;
        }
        int index = 0;
        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] != 0) {
                for (int j = 0; j < bucket[i]; j++) {
                    /**
                     * 上一步桶的编号减去了最小值
                     * 这一步需要把减去的最小值补偿回来
                     */
                    arr[index++] = (i+min);
                }
            }
        }
        return arr;
    }

    /**
     * 适用与正数，求最大值
     * @param arr
     * @return
     */
    static int getArrCount(int arr[]) {
        int max = 0;
        int min = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max + 1;
    }

    /**
     * 适用于数组里面带负数
     * 0 为数组大小，1为最小数，2为最大数
     *
     * @param arr
     * @return
     */
    static int[] getArrCountF(int arr[]) {
        int[] returnArr = {0, 0, 0};
        int max = 0;
        int min = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        returnArr[0] = max - min + 1;
        returnArr[1] = min;
        returnArr[2] = max;
        return returnArr;
    }
}
